This invention relates generally to geometric modeling using polygonal meshes for computer graphics, and more particularly to a progressive hulls data structure for modeling the outer surface geometry of a three-dimensional object in varying degrees of resolution, with the property that each lower resolution hull encompasses the higher resolution hull(s) from which it was derived.
In a computer graphics system, it is desirable to represent an object as efficiently as possible to preserve memory and system bandwidth, and to enhance rendering speed. Computer graphics, such as in computer generated images, animations and effects for motion pictures, television, computer multi-media, computer games, print and other media, often employ detailed geometric models for rendering images of three-dimensional (3D) objects. These models are typically created using commercially available computer-aided modeling and 3D scanning systems. Although some geometric models may be initially defined using high level primitives, for efficient rendering they are typically converted to their lowest common denominator form, polygonal approximations called meshes.
In the simplest case, a mesh consists of a set of vertices and a set of faces. Each vertex specifies the (x,y,z) coordinates of a point in space, and each face defines a polygon by connecting together an ordered subset of the vertices. These conjoined polygons approximate the surface geometry of the modeled object. The polygons may in general have arbitrary numbers of vertices (and even holes). For convenience, the special case of a mesh (called a xe2x80x9ctriangle meshxe2x80x9d) in which all faces have exactly three vertices is commonly used. Arbitrary meshes composed of polygons having faces with any number of vertices equal to or greater than three can be easily converted to triangle meshes through known triangulation processes.
In the following discussion, the geometry of a triangle mesh is denoted by a tuple (K, V), where K is a simplicial complex specifying the connectivity of the mesh simplices (i.e., the adjacency of the vertices, edges, and faces), and V={v1, . . . , vm} is the set of vertex positions vj=(xj,yj,zj) defining the shape of the mesh in R3. More precisely, a parametric domain, |K|⊂Rm, is constructed by identifying each vertex of K with a canonical basis vector of Rm, and the mesh is defined as the image, xcfx86v(|K|), where xcfx86v:Rmxe2x86x92R3 is a linear map. (See, e.g., H. Hoppe et al., Mesh Optimization, 1993 Computer Graphics Proceedings 19-26; hereinafter referred to as Hoppe93.) An exemplary mesh 80 is shown in FIG. 2. The vertices of a triangle mesh (e.g., vertices 82-89 of the mesh 80) are denoted as v1, . . . , vm; the edges (e.g., 92-95) are denoted by pairs of adjacent vertices as e={vj,vk}; and the faces (e.g., faces 100-107) are denoted by triples of interconnected vertices as f={vj,vk,vl}.
Complex (i.e., highly detailed) triangle meshes are notoriously difficult to render, store, and transmit. The meshes created by modeling and scanning systems are typically not optimized for display performance. In most applications, these initial meshes can usually be replaced by nearly indistinguishable approximations with far fewer faces, thereby improving rendering efficiency. One approach to speed up rendering is to replace a complex mesh by a set of level-of-detail (LOD) approximations. A detailed mesh is used when the object is close to the viewer, and coarser approximations (i.e., meshes with fewer vertices and faces) are substituted as the object recedes from the viewer in the image. These LOD approximations can be precomputed automatically using known mesh simplification methods. Thus, a fully detailed mesh is used when the object is close; and coarser approximations are substituted as the object recedes. Instantaneous switching between two LOD approximations of a given model can lead to a perceptible xe2x80x9cpoppingxe2x80x9d display effect. For this reason, the capability of constructing smooth visual transitions, called geomorphs, between meshes having different levels of detail is desirable.
A model should be stored in the smallest amount of memory or disk space. Two schemes have been developed to deal with this problem. One is to use mesh simplification, as described earlier, to reduce the number of faces in the model as much as possible while preserving its appearance. The other is mesh compression: minimizing the space taken to store the model, given that a particular mesh has been selected.
Co-pending application titled Progressive Meshes, U.S. patent application Ser. No. 08/586,953, filed Jan. 11, 1996, commonly assigned and incorporated herein by reference hereinafter referred to as Hoppe ""953), describes a progressive mesh (PM) representation which provides a unified solution to the problems of efficiently storing, transmitting and rendering a mesh of arbitrary complexity. In short, the PM representation of an arbitrary mesh M is stored as a coarse or base mesh M0 together with a sequence of n refinement records that indicate how to incrementally refine M0 back up to the arbitrary mesh M. Each refinement record encodes information associated with a vertex split transformation that transforms the mesh by splitting a vertex vs (positioned between side vertices vl and vr, as shown, for example, in FIG. 2) to add one vertex vt and up to two faces (fl={vs,vt,vl} and (fr={vs,vt,vr}) to the mesh. The PM representation thus defines a continuous sequence of LOD approximations to the arbitrary mesh that are produced by applying the vertex split transformation defined by successive refinement records successively to the base mesh M0, resulting in a sequence of progressively more detailed meshes M0 . . . Mn,Mn=M. In other words, the PM representation of M thus defines a continuous sequence of meshes M0,M1, . . . ,Mn of increasing accuracy from which LOD approximations with a desired complexity can be efficiently retrieved.
FIG. 2 shows the vertex split transformation and its inverse, the edge collapse transformation. As shown in FIG. 2, each edge collapse transformation unifies two adjacent vertices into one, thereby removing two faces from the mesh. For the purpose of level-of-detail control, edge collapses are selected so as to best preserve the appearance of the mesh during simplification. Several appearance metrics have been developed and are described in, for example, Cohen et al., Appearance-Preserving Simplification, Computer Graphics (SIGGRAPH ""98 Proceedings) (1998), 115-122, Garland and Heckbert, Surface Simplification Using Quadric Error Metrics, Computer Graphics (SIGGRAPH ""97 Proceedings) (1997), 209-216, and Hoppe, Progressive Meshes, Computer Graphics (SIGGRAPH ""96 Proceedings) (1996), 99-108.
The PM representation also supports smooth visual transitions, or geomorphs, between any two of these approximations, as well as allowing progressive transmission and efficient compression of the sequence of LOD approximations of the arbitrary mesh. In addition, the PM representation naturally supports progressive transmission, offers a concise encoding of M itself, and supports efficient selective refinement. In short, the PM representation offers an efficient, lossless, continuous-resolution representation. Thus, when rendering an image of a three-dimensional object, it is possible to reduce the amount of data needed to represent the geometry of the object without sacrificing much in terms of the quality of the resulting image, by using a simplified mesh created by collapsing selected edges of a higher resolution mesh.
For realistic rendering of an object, meshes in computer graphics (including the continuous sequence of LOD meshes defined by the PM representation) often have numerous other appearance attributes in addition to their geometric properties (i.e., vertex positions and connectivity of vertices and polygons). These additional appearance attributes can be classified into two types, discrete attributes and scalar attributes.
There are applications involving computer graphics in which it is necessary or desirable to provide a low resolution mesh representation of an object with the property that the volume defined by the low resolution mesh is larger than and contains the volume defined by a higher resolution, more detailed representation of the object. Such applications include silhouette clipping and collision detection. The PM technique does not necessarily meet this need since the progressive meshes do not necessarily enclose a volume that is larger than the original geometry.
The present invention provides computer based methods and systems for generating a sequence of data structures, or progressive hulls, that model the outer surface geometry of a three-dimensional object to be rendered. According to the invention, a first mesh representation of the object is formed, and then second mesh representation of the object is then formed. Importantly, the second mesh comprises a fewer number of vertices than the first mesh (i.e., is less detailed than the first mesh), and encloses a volume that contains the volume defined by the first mesh. These mesh representations of the three-dimensional object, referred to as hulls, represent the external visible apparent contour of the object, just as a silhouette represents the external contour of a two-dimensional object.
The second mesh representation of the object may be generated by performing an edge collapse transformation involving a reduction of two vertices into a single new vertex. Preferably, the edge collapse transformation comprises determining a set of permissible positions for the new vertex, selecting one of the permissible positions based on a minimization constraint, and collapsing the edge using the selected position for the new vertex.
The edge to be collapsed will typically be touched by a plurality of face planes. The set of permissible positions for the new vertex may be based on the constraint that, as the edge is collapsed, the new vertex generated by the collapse is placed in a volume defined by the intersection of the half spaces above the face planes touching the edge.
The minimization constraint mentioned above seeks to minimize the difference in volume between the second mesh and the first mesh.
Additional features and advantages of the invention will be made apparent from the following detailed description of an illustrated embodiment.